@include "misc.awk"

function sorted(pairs,s,    i,n) {
    sorter0(pairs,s)
    sorter1(s)  
}
function sorter0(pairs,s,_small,  key,x) {
    _small = the(_small,100)
    for(key in pairs) {
        x = pairs[key] + rand()/_small
        s["all"] += x
        s["value"][key] = x
        s["index"][x] = key
}}
function sorter1(s,   i,n,sorted,one, some) {
    n=asort(s["value"],sorted)
    for(i=1;i<=n;i++) {
        one  = s["best"][i] =  s["index"][sorted[i]]
        some += sorted[i]
        s["cdf"][i]  =  some/s["all"]
}}
function best2val(s,b)  { return s["value"][s["best"][b]]  }
function best2key(s,b)  { return s["best"][b] }
function key2val(s,key) { return s["value"][key] }
function val2key(s,val) { return s["index"][val] }

#skew > 1, favor lower prob. skew<1,favor higher prob
function pick(s,_skew,   i) { 
    i = pick1(s, the(_skew,1), s["cdf"])
    return s["best"][i]
}
function pick1(s,skew,cdf,   what,u,i,sofar) {
    u = rand() ^ skew
    for(i=length(cdf)-1; i>=1; i--) 
        if(u > cdf[i])
            return i+1
    return 1
}
